/**
 * @Description: 最大连续1的个数 III
 * 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，
 * 则返回 数组中连续 1 的最大个数 。
 * @Date:Create in 22:17  2022/7/25
 */
public class longestOnes1004 {

    public static void main(String[] args) {
        int[] nums ={0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
        int k = 3;
        System.out.println(longestOnes(nums,k));
    }

    //滑动窗口
    public static int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int left=0,lsum=0,rsum=0;
        int len =0;
        for(int right=0;right<n;++right){
            rsum += 1-nums[right];
            while(lsum < rsum-k){
                lsum += 1 -nums[left];
                ++left;
            }
            len = Math.max(len,right-left+1);
        }
        return len;
    }

    //!!!超出时间限制
    public static int longestOnes2(int[] nums, int k) {
        if (nums == null) return 0;
        int left = 0,len = 0;
        for (int i = left; i < nums.length; i++) {
            int a = k;
            int right = i;
            int len1 = 0;
            while(nums[left]!=1 && left<nums.length){
                left++;
            }
            while(a>0 && right<nums.length){
                if(nums[right]==0) a--;
                right++;
                len1++;
            }
            if(right<nums.length-1 && nums[right]==1){
                for(int j=right;j<nums.length;j++){
                    if(nums[j]==1) len1++;
                    else break;
                }
            }

            len = Math.max(len1,len);
        }
        return len;
    }
}
